// 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
// 回溯
// 回溯来做做
// nums = [1,5,11,5] => true
// nums = [1,2,3,5] => false
// const canPartition = (nums) => {
//     let len = nums.length
//     let sum = nums.reduce((pre, next) => pre + next)
//     let sum2 = sum / 2
//     if (sum % 2 !== 0) {
//         return false
//     }
//     // 第一个参数肯定是当前的和，用做递归边界
//     function partition(curSum, nth) {
//         let map = new Map()
//         if (curSum == sum2) {
//             return true
//         }
//         if (curSum > sum2 || nth == len) {
//             return false
//         }
//         let key = curSum + '&' + nth
//         console.log(key);
//         if (map.has(key)) {
//             return map.get(key)
//         }
//         let res = partition(curSum + nums[nth], nth + 1) || partition(curSum, nth + 1)
//         map.set(key, res)
//         return res
//     }

//     return partition(0, 0)
// }
// let nums = [100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 99, 97]
// 给定这个参数时，会超时







console.log(canPartition(nums));

